package com.justnow.offer;

import java.util.HashSet;

/**
 * @author justnow
 * Created on 2020-08-14
 * Description
 */
public class Solution57_1 {

    /**
     * 方法一，使用hashset
     * 时间复杂度：O(N)
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        for (int n : nums) {
            int e = target - n;
            if (set.contains(e)) {
                return new int[] {n, e};
            }
        }
        // 如果找不到的话，直接返回一个空的数组
        return new int[]{};
    }

    /**
     * 方法二，使用双指针方法
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum2(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] == target)
                return new int[]{nums[left], nums[right]};
            else if (nums[left] + nums[right] < target)
                left++;
            else
                ++left;
        }
        return new int[]{};
    }

    /**
     * 方法三，使用二分法
     * @param nums
     * @param target
     * @return
     */
/*
    public int[] twoSum3(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            int left = i + 1, right = nums.length - 1, e = target - nums[i];
        }
    }
*/
}
